//单链表
#ifndef __SINGLYLINKEDLIST__CPP
#define __SINGLYLINKEDLIST__CPP

#include"VirtualLinkedList.hpp"

namespace NgSiuKei {
    
template<class TheClass>
struct sigly_linked_list_node {
    TheClass val;
    sigly_linked_list_node<TheClass> *next;//后一个
};
#define sll_node sigly_linked_list_node

template<class TheClass>
class SinglyLinkedList: public VirtualLinkedList<TheClass> {
    public:
    SinglyLinkedList(void);
    ~SinglyLinkedList(void);

    public:
    //清空
    void clear(void);
    //获取特定下标的元素值
    TheClass getVal(const U_L_L &index) const;
    //查找数据，返回下标，表没有则抛出异常：EXCEPTION_CAN_NOT_FIND
    U_L_L findVal(const TheClass &val) const;
    //插入数据
    void insertVal(const TheClass &val, const U_L_L &index);
    //删除特定下标的元素，返回元素值
    TheClass deleteWithIndex(const U_L_L &index);
    //打印表
    void print(void);

    private:
    sll_node<TheClass> *node;
};

template<class TheClass>
SinglyLinkedList<TheClass>::SinglyLinkedList(void): VirtualLinkedList<TheClass>() {
    this->node = nullptr;
}

template<class TheClass>
SinglyLinkedList<TheClass>::~SinglyLinkedList(void) {
    this->clear();
}

template<class TheClass>
void SinglyLinkedList<TheClass>::clear(void) {
    sll_node<TheClass> *currentNode = nullptr;
    while(nullptr != this->node) {
        currentNode = this->node;
        this->node = this->node->next;
        delete currentNode;
        currentNode = nullptr;
    }
    this->node = nullptr;
    this->size = 0;
}

template<class TheClass>
TheClass SinglyLinkedList<TheClass>::getVal(const U_L_L &index) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index >= this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    sll_node<TheClass> *currentNode = this->node;
    for(U_L_L i=1; i<=index; ++i) {
        currentNode = currentNode->next;
    }
    return currentNode->val;
}

template<class TheClass>
U_L_L SinglyLinkedList<TheClass>::findVal(const TheClass &val) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }

    U_L_L resultIndex = 0;
    sll_node<TheClass> *currentNode = this->node;
    while(nullptr != currentNode) {
        if(val == currentNode->val) {
            return resultIndex;
        }
        ++resultIndex;
        currentNode = currentNode->next; 
    }
    throw EXCEPTION_CAN_NOT_FIND;
}

template<class TheClass>
void SinglyLinkedList<TheClass>::insertVal(const TheClass &val, const U_L_L &index) {
    if(index > this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    this->size++;
    sll_node<TheClass> *newNode = new sll_node<TheClass>;
    newNode->val = val;

    if(index == 0) {//头
        newNode->next = this->node;
        this->node = newNode;
    }
    else if(index == this->size) {//尾
        sll_node<TheClass> *currentNode = this->node;
        while(nullptr != currentNode->next) {
            currentNode = currentNode->next;
        }
        currentNode->next = newNode;
    }
    else {
        sll_node<TheClass> *prevNode = this->node;
        for(U_L_L i=1; i<index; ++i) {
            prevNode = prevNode->next;
        }
        sll_node<TheClass> *nextNode = prevNode->next;
        prevNode->next = newNode;
        newNode->next = nextNode;
    }
}

template<class TheClass>
TheClass SinglyLinkedList<TheClass>::deleteWithIndex(const U_L_L &index) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index >= this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    this->size--;
    sll_node<TheClass> *deleteNode = nullptr;
    if(index == 0) {//头
        deleteNode = this->node;
        this->node = this->node->next;
    }
    else if(index == this->size-1) {//尾
        sll_node<TheClass> *currentNode = this->node;
        while(nullptr != currentNode->next->next) {
            currentNode = currentNode->next;
        }
        deleteNode = currentNode->next;
        currentNode->next = nullptr;
    }
    else {
        sll_node<TheClass> *prevNode = this->node;
        for(U_L_L i=1; i<index; ++i) {
            prevNode = prevNode->next;
        }
        deleteNode = prevNode->next;
        prevNode->next = deleteNode->next;
        deleteNode->next = nullptr;
    }
    
    TheClass resultVal;
    if(nullptr != deleteNode) {
        resultVal = deleteNode->val;
        delete deleteNode;
        deleteNode = nullptr;
    }
    return resultVal;
}

template<class TheClass>
void SinglyLinkedList<TheClass>::print(void) {
    cout << "打印单链表：[ ";
    sll_node<TheClass> *currentNode = this->node;
    while(nullptr != currentNode) {
        cout << currentNode->val << ' ';
        currentNode = currentNode->next;
    }
    cout << ']' << endl;
}

}

#endif